class Graph:
    def __init__(self, v_num=0, e_num=0, labels=None):
        self.v_num = v_num    # 节点数量
        self.e_num = e_num    # 边数量
        self.g = [dict()]*v_num    # 图结构，链表 g[u]: {v:distance}
        self.node = []        # 节点名称，即教室编号、楼梯口编号等

        self.horizon = set()    # 保存东西关系节点对
        self.vertical = set()    # 保存上下关系节点对

        if labels:
            self.node = label
            self.vlookup = dict(zip(self.node, range(self.v_num)))
        else:
            self.vlookup = dict()

    def addNode(self, label):
        v_id = self.v_num
        self.node.append(label)
        self.g.append(dict())
        if label not in self.vlookup:
            self.vlookup[label] = v_id

        self.v_num += 1

    # 图上两个节点添加一条边 
    # dire = 0 | walk | up
    # 0: u==v
    # walk: u->v 东西向
    # up: u->u 上下楼
    def addEdge(self, u, v, d, dire=0):
        u_id = self.vlookup.get(u, -1)
        v_id = self.vlookup.get(v, -1)

        if u==-1 or v==-1:
            print("节点不存在")
            return
        else:
            self.g[u_id][v_id] = d
            self.g[v_id][u_id] = d

            # 记录相对位置
            if dire=='walk':
                self.horizon.add((u_id, v_id))
            elif dire=='up':
                self.vertical.add((u_id, v_id))

# 返回从起点到终点的最短路径
def dijkstra(graph, start, end):
    start = graph.vlookup.get(start, -1)
    end = graph.vlookup.get(end, -1)
    if start==-1:
        return "起点有误"
    if end==-1:
        return "教室编号不存在"

    dis = [99999] * graph.v_num
    path = [-1] * graph.v_num
    vis = [False] * graph.v_num

    from queue import PriorityQueue
    pq = PriorityQueue()

    dis[start] = 0
    pq.put((0, start))

    while pq.qsize()>0:
        dis_now, u_now = pq.get()
        
        if vis[u_now]:
            continue

        vis[u_now] = True

        for v_to, dist_uv in graph.g[u_now].items():
            if not vis[v_to] and dis_now + dist_uv < dis[v_to]:
                dis[v_to] = dis_now + dist_uv
                path[v_to] = u_now

                pq.put((dis[v_to], v_to))

    # 找到从 start 到 end的路径
    route = [end]
    pre = path[end]
    while pre != start:
        route.insert(0, pre)
        pre = path[pre]
    route.insert(0, start)

    # 生成导航指令
    instructions = []
    now = start
    for u in route[1:]:  # 跳过起点
        label = graph.node[u]
        if label.startswith('st'):
            label = '通道口' + label[2:]
        elif label.endswith('x'):
            now = u
            continue

        if (now, u) in graph.horizon:
            instructions.append(f"往西走到{label}")
        elif (u, now) in graph.horizon:
            instructions.append(f"往东走到{label}")
        elif (now, u) in graph.vertical:
            instructions.append(f"上楼走到{label}")
        elif (u, now) in graph.vertical:
            instructions.append(f"下楼走到{label}")
        else:
            instructions.append(f"走到{label}")
        now = u

    # 添加起点信息
    if graph.node[start].startswith('st'):
        instructions.insert(0, f"从通道口{graph.node[start][2:]}出发")

    # 返回路径和距离
    return {
        'route': [graph.node[i] for i in route],
        'distance': dis[end],
        'instructions': instructions
    }